/**
 * @file   Tree.h
 * @author xingyifan
 * @date   2021/08/19 11:25:17
 * 
 * @brief  here are the trees
 * 
 * 
 */

#include "Tree.h"

#ifndef __BINARY__TREE__
#define __BINARY__TREE__

typedef Binary_Node<T> Bnode;

class Binary_Tree
{
private:
    u_int size;
    Bnode *root;
    static u_int count; //计数
    static Bnode *nil;  //只需要一个nil

    void inorder_walk(ostream &, Bnode *) const; //print the tree
    Bnode *successor(Bnode *);                   //test the value next
    Bnode *predeccessor(Bnode *);                //test the last value
    Bnode *max(Bnode *);
    Bnode *min(Bnode *);
    Bnode *find_node(T);
    Bnode *get(int, int) const;         //根据深度和横坐标获取元素
    void change_size(Bnode *, Bnode *); //change the size from tail to head
    void replace(Bnode *, Bnode *);     //v替换u，u的父节点指向v，v的父节点指向u的父节点
    int height(Bnode *) const;
    void clean(Bnode *); //clean the tree

public:
    Binary_Tree()
    {
        size = 0;
        if (count == 0)
        {
            nil = new Bnode;
        }
        root = nil;
        count++;
    }
    Binary_Tree(u_int len, T A[]) : Binary_Tree()
    {
        for (int i = 0; i < len; i++)
        {
            insert(A[i]);
        }
    }

    void insert(T); //insert node
    void remove(T); //delete node

    friend ostream &operator<<(ostream &out, const Binary_Tree &bt)
    {
        bt.inorder_walk(out, bt.root);
        return out;
    }

    T operator[](int i) const
    {
        Bnode *p = root;
        if (i < 0)
        {
            i += size;
        }
        if (i >= 0 && i < size)
        {
            int index = p->lc->size;
            while (index != i)
            {
                if (index < i)
                {
                    p = p->rc;
                    index += p->lc->size + 1;
                }
                else
                {
                    p = p->lc;
                    index -= p->rc->size + 1;
                }
            }
            return p->value;
        }
        return NONE;
    }

    T min() { return min(root)->value; }
    T max() { return max(root)->value; }
    int indexOf(T);
    void perfect_draw() const; //print a perfect tree
    void draw() const;         //print the tree
    int get_h() const { return height(root); }

    ~Binary_Tree()
    {
        clean(root);
        count--;
        if (count == 0)
        {
            delete nil;
            nil = NULL;
        }
    }
};

#endif
